//使用简易并查集
class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        vector<int> ufs(isConnected.size(), -1);

        auto findRoot = [&ufs](int x) -> int {
            while (ufs[x] >= 0) {
                x = ufs[x];
            }
            return x;
        };

        auto unionSet = [&ufs, &findRoot](int x, int y) {
            int rootX = findRoot(x);
            int rootY = findRoot(y);
            if (rootX != rootY) {
                if (ufs[rootX] <= ufs[rootY]) {
                    ufs[rootX] += ufs[rootY];
                    ufs[rootY] = rootX;
                } else {
                    ufs[rootY] += ufs[rootX];
                    ufs[rootX] = rootY;
                }
            }
        };

        for (size_t i = 0; i < isConnected.size(); ++i) {
            for (size_t j = 0; j < isConnected[i].size(); ++j) {
                if (isConnected[i][j] == 1 && i != j) {
                    unionSet(i, j);
                }
            }
        }

        int count = 0;
        for (int i = 0; i < ufs.size(); ++i) {
            if (ufs[i] < 0) {
                ++count;
            }
        }
        return count;
    }
};
